package code.oldCode.feishuSpecializedTraining.greedy;

import java.util.*;

/**
 * @author 26029
 * @date 2025/3/19
 * @description
 */
public class MyGreedy5 {
    // 435. 无重叠区间
    public int eraseOverlapIntervals(int[][] intervals) {
        // 排序+贪心，O(nlog2n)
        // 思路是，O(n)的遍历interval，当前节点指最长不相交子序列的节点，与下一个比较，
        // 如果不相交，则当前节点更新为这个节点
        // 如果相交，则选择右侧值小的作为新节点（贪心），同时确定，新加一个移除项
        int len = intervals.length;
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
            else
                return Integer.compare(o1[1], o2[1]);
        });
        int[] now = intervals[0];
        int remove = 0;
        for (int i = 1; i < len; i++) {
            // 如果有交集，删一个
            if (now[1] > intervals[i][0]) {
                // 选择右面比较小的继续（贪心）
                if (now[1] > intervals[i][1])
                    now = intervals[i];
                remove++;
            }
            // 没交集，继续遍历下一个
            else {
                now = intervals[i];
            }
        }
        return remove;
    }

    public int eraseOverlapIntervals_dp(int[][] intervals) {
        // 尝试用动态规划，时间复杂度是O(n^2)，leetcode超时，不过作为一种思路吧
        // 先求最长不重叠子序列长度，这个最长，要减掉的序列就越少，答案就是 序列数-最长不重叠子序列长度
        int len = intervals.length;
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
            else
                return Integer.compare(o1[1], o2[1]);
        });
        int[] dp = new int[len]; // dp[i]表示以i结尾的最长不重叠子序列的长度
        Arrays.fill(dp, 1); // dp[i] =
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return len - Arrays.stream(dp).max().getAsInt();
    }

    // 763. 划分字母区间
    public List<Integer> partitionLabels(String s) {
        // thinking:找到每个字母的最早和最晚出现的位置，形成一个part = [start, end]。
        // 找到所有相交part组成的片段，比如ababcbacadefegdehijhklij有三个片段ababcbaca、defegde、hijhklij
        // 简而言之：合并区间
        int len = s.length();
        List<Integer> list = new ArrayList<>();
        // 填充map
        Map<Character, Integer> mapLeft = new HashMap<>(), mapRight = new HashMap<>();
        for (int i = 0; i < len; i++) {
            Character c = s.charAt(i);
            if (!mapLeft.containsKey(c)) {
                mapLeft.put(c, i);
            }
        }
        for (int i = len - 1; i >= 0; i--) {
            Character c = s.charAt(i);
            if (!mapRight.containsKey(c)) {
                mapRight.put(c, i);
            }
        }
        // 得到parts
        int[][] parts = new int[mapLeft.size()][2];
        int i = 0;
        for (Character key : mapLeft.keySet()) {
            int[] part = new int[]{mapLeft.get(key), mapRight.get(key)};
            parts[i] = part;
            i++;
        }
        // 给parts排序
        Arrays.sort(parts, (o1, o2) -> {
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
            else
                return Integer.compare(o1[1], o2[1]);
        });
        // 找组，这个组的范围越来越大，直到与后面的part完全分离
        int[] now = new int[]{parts[0][0], parts[0][1]};
        for (int j = 1; j < parts.length; j++) {
            if (now[1] > parts[j][0]) {
                now[0] = Math.min(now[0], parts[j][0]);
                now[1] = Math.max(now[1], parts[j][1]);
            } else {
                list.add(now[1] - now[0] + 1);
                now[0] = parts[j][0];
                now[1] = parts[j][1];
            }
        }
        list.add(now[1] - now[0] + 1);

        return list;
    }

    public List<Integer> partitionLabels_official(String s) {
        // 用类似“跳跃游戏”的方法
        int len = s.length();
        List<Integer> list = new ArrayList<>();
        // 记录最后出现的位置
        Map<Character, Integer> cLastPos = new HashMap<>();
        for (int i = len - 1; i >= 0; i--) {
            if (!cLastPos.containsKey(s.charAt(i)))
                cLastPos.put(s.charAt(i), i);
        }
        // 遍历s
        int start = 0;
        int target = 0;
        for (int i = 0; i < len; i++) {
            target = Math.max(target, cLastPos.get(s.charAt(i)));
            if (i == target) {
                list.add(target - start + 1);
                start = i + 1;
            }
        }
        return list;
    }

    // 56. 合并区间
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        List<int[]> okInterval = new ArrayList<>();
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] != o2[0])
                return Integer.compare(o1[0], o2[0]);
            else
                return Integer.compare(o1[1], o2[1]);
        });

        int[] now = new int[]{intervals[0][0], intervals[0][1]};
        for (int i = 1; i < len; i++) {
            if (now[1] >= intervals[i][0]) {
                now[1] = Math.max(now[1], intervals[i][1]);
            } else {
                okInterval.add(new int[]{now[0], now[1]});
                now[0] = intervals[i][0];
                now[1] = intervals[i][1];
            }
        }
        okInterval.add(new int[]{now[0], now[1]});

        int[][] ans = new int[okInterval.size()][2];
        for (int i = 0; i < okInterval.size(); i++) {
            ans[i] = okInterval.get(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        MyGreedy5 m = new MyGreedy5();
        String s = "eccbbbbdec";
        System.out.println(m.partitionLabels(s));
    }
}
